package com.github.yangyishe.p400;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 347. 前 K 个高频元素
 * https://leetcode.cn/problems/top-k-frequent-elements/description/?envType=study-plan-v2&envId=top-100-liked
 *
 * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
 *
 *
 *
 * 示例 1:
 *
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 * 示例 2:
 *
 * 输入: nums = [1], k = 1
 * 输出: [1]
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 105
 * k 的取值范围是 [1, 数组中不相同的元素的个数]
 * 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
 *
 *
 * 进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
 */
public class Problem347 {
    public static void main(String[] args) {
        int[] nums=new int[]{-1,1,4,-4,3,5,4,-2,3,-1};
        int k=3;

        Problem347 problem347 = new Problem347();
        int[] topKFrequent = problem347.topKFrequent(nums, k);
        System.out.println("Arrays.toString(topKFrequent) = " + Arrays.toString(topKFrequent));

    }

    /**
     * 思路：
     * 最直接的思路，是将数组进行排序，然后获取前k个元素。
     * 比较简单，不再演示。这里直接做进阶要求。
     *
     * 原来的思路中，有两部分信息，实际是浪费的，一是并不要求这k个元素按照顺序排列，二是只需要k个元素，不需要其他的。
     *
     * 可以考虑使用堆栈解决。
     * 先使用map将元素与其频率收集起来，之后按照entry作为对象，启用top-k思路
     *
     * 对于堆栈处理top-k，最重要的是写好两个方法：
     * 1、对一个随机排列的数组，进行堆化；（此处应是小顶堆）
     * 2. 小顶堆的堆顶元素更换后，重新堆化；
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> numCountMap=new HashMap<>();
        for (int num : nums) {
            numCountMap.put(num,numCountMap.getOrDefault(num,0)+1);
        }

        Map.Entry<Integer,Integer>[] entries=new Map.Entry[k];
        int index=0;
        boolean hasTop=false;
        for (Map.Entry<Integer, Integer> entry : numCountMap.entrySet()) {
            if(index<k){
                entries[index++]=entry;
            }else{
                if(!hasTop){
                   constructTopK(entries);
                   hasTop=true;
                }
                // 比较变换
                Map.Entry<Integer, Integer> topEntry = entries[0];
                if(topEntry.getValue()<entry.getValue()){
                    entries[0]=entry;
                    keepTopKRoot(entries,0);
                }

            }
        }
        if(!hasTop){
            constructTopK(entries);
        }

        int[] result=new int[k];
        int r=0;
        for(Map.Entry<Integer,Integer> entry:entries){
            result[r++]=entry.getKey();
        }

        return result;
    }

    /**
     * 构建top-k数组
     * 创建一个小顶堆。从队尾开始，维护小顶堆，以此保证某个元素的左右子树都是小顶堆。
     *
     * @param entries
     */
    private void constructTopK(Map.Entry<Integer,Integer>[] entries){
        //从尾部开始变化
        for(int i= entries.length-1;i>=0;i--){
            keepTopKRoot(entries,i);
        }
    }

    /**
     * 在左右子树都是小顶堆的情况下，保证top是小顶堆
     * @param entries
     * @param top
     */
    private void keepTopKRoot(Map.Entry<Integer, Integer>[] entries,int top){
        int left=top*2+1;
        int right=top*2+2;

        if(left>=entries.length){
            return;
        }
        if(right>= entries.length){
            cas(entries,top,left);
            return;
        }

        if(entries[left].getValue()< entries[right].getValue()){
            cas(entries,top,left);
            keepTopKRoot(entries,left);
        }else{
            cas(entries,top,right);
            keepTopKRoot(entries,right);
        }

    }

    /**
     * 比较并切换。保证前面的元素小于后面的元素
     * 最基础的操作方法
     * @param entries
     * @param before
     * @param after
     */
    private void cas(Map.Entry<Integer, Integer>[] entries, int before, int after) {
        if(entries[before].getValue()>entries[after].getValue()){
            Map.Entry<Integer,Integer> tmp=entries[before];
            entries[before]=entries[after];
            entries[after]=tmp;
        }
    }

}
